Syarikat ini didaftarkan pada Tahun 2016 di Kementerian Hal Ehwal Ekonomi Taiwan . [2] Perkara ini disahkan oleh Chang Kuo-wei pada Tarikh 30 November 2016, yang sebelumnya merupakan ketua syarikat penerbangan Taiwan iaitu Syarikat Penerbangan EVA Air . [3] Syarikat penerbangan itu berdaftar dengan Pentadbiran Aeronautik Awam Taiwan pada separuh pertama Tahun 2017, [4] dan telah dirancang, pada akhir 2016, syarikat penerbangan itu akan mula beroperasi pada Tahun 2018. [5] Kementerian Hal Ehwal Ekonomi Taiwan menerima permohonan rasmi untuk menubuhkan syarikat penerbangan dengan nama Starlux Airlines pada Tarikh 22 Mei 2017. [6] Dalam temu bual pada Tahun 2017, syarikat penerbangan itu dijangka mula beroperasi pada akhir 2019, [7] walaupun pada Januari 2019, Chang menyatakan bahawa Penerbangan Starlux akan dilancarkan pada Januari 2020. [8]

Pada Bulan Mac 2019, ketua syarikat penerbangan STARLUX Airlines Chang Kuo-wei menandatangani tempahan untuk 17 buah pesawat Airbus A350 XWB, yang juga merupakan perjanjian pembelian Airbus tunggal terbesar di negara ini. [2] Pada Bulan September 2019, syarikat penerbangan itu mengumumkan destinasi pertama yang akan dilancarkan, yang terdiri daripada Da Nang, Makau, dan Pulau Pinang yang akan bermula pada Tarikh 23 Januari 2020. [9] Pada Tarikh 25 Oktober 2019, pesawat pertama syarikat penerbangan, bersiri Airbus A321neo, dihantar dari Hamburg, Jerman, sebelum pesawat tiba di hab syarikat penerbangan di Lapangan Terbang Antarabangsa Chiang Kai Shek pada 29 Oktober selepas berhenti di Dubai dan Bangkok. [10] Pada 10 Disember 2019, Penerbangan Starlux menerima sijil pengendali udaranya (AOC) dari Pentadbiran Aeronautik Sivil Taiwan, diikuti dengan pembukaan tempahan secara rasmi pada Tarikh 16 Disember 2019 untuk permulaan perkhidmatan pada bulan berikutnya. [11] [12]

Oleh kerana Pandemik COVID-19 dan kesannya terhadap penerbangan, yang mulai terjadi dalam beberapa bulan sejak pelantikan syarikat penerbangan itu, Penerbangan Starlux mengumumkan penangguhan sebahagian besar perkhidmatannya kecuali kepada Da Nang. [13] Selepas itu, pada Bulan Mac 2020 syarikat penerbangan menangguhkan semua operasinya sehingga Tarikh 2 Jun 2020, [14] setelah itu syarikat penerbangan itu meneruskan perkhidmatan tiga minggu ke Makau. [15] Sebelum syarikat penerbangan menyambung semula perkhidmatannya, pihaknya menerima izin pada Mei 2020 untuk memulakan perkhidmatan ke Naha sebagai destinasi pertama di Jepun, dengan tarikh permulaan tidak lebih awal dari 1 Julai, namun syarikat penerbangan itu mengatakan bahawa garis masa untuk pelantikan perkhidmatan Naha bergantung pada wabah perkembangan. [16] Selepas wabak tersebut, syarikat penerbangan itu juga melambatkan pelancaran perkhidmatan Cebu dua kali, dan menangguhkan pelancaran perkhidmatannya ke Naha sampai bila-bila.